{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 线性表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "线性表是一些元素的存储序列，它维持这元素之间的一种线性关系，它能够找到表中的首元素，并且能够从表中任一元素出发，可以找到它之后的下一个元素。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 顺序表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### 定义：将表中元素顺序地存储在一大块连续的存储空间里，元素间的顺序关系由它们的存储顺序自然表示。\n",
    "\n",
    "<img src=\"image/chapter01/1531909-341d40e2192a1a70.png\" width=600>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 优点：O(1)的时间按位置直接访问元素，元素在表里存储紧密，不会产生空间碎片。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 缺点：如果初始的存储空间很大，而仅保存了少量数据，就会有大量的空闲单元搁置。另外，在执行插入和删除操作时可能需要移动大量元素，效率低下。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 创建操作 O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "创建空表时，需要分配一块元素进行存储，记录表的容量和个数，即设置好 max 和 num=0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "seq = list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### 访问操作 O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "访问下标第 i 个元素时，需要检查 i 的值是否在表的合法元素范围内。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "seq[1]: 2\n",
      "len(seq): 3\n"
     ]
    }
   ],
   "source": [
    "seq = [1,2,3]\n",
    "print(\"seq[1]: {}\".format(seq[1])) # 访问下标为 1 的元素\n",
    "print(\"len(seq): {}\".format(len(seq))) # 访问表中元素的个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 插入操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "【1】 中间插入 O(n) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[1, 5, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "print(seq)\n",
    "seq.insert(1,5) # 将元素“5”插在下标为1的位置\n",
    "print(seq)  # 元素“5”之后的元素下标都往后移动了1位"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "【2】 尾端插入 O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 2, 3, 6]\n"
     ]
    }
   ],
   "source": [
    "seq.append(6)\n",
    "print(seq) # 元素“6”之前的元素下标并未发生改变"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 删除操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "【1】 pop 函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 2, 3, 6]\n",
      "[1, 2, 3, 6]\n"
     ]
    }
   ],
   "source": [
    "print(seq)\n",
    "seq.pop(1) # 删除下标为 1 的元素，时间复杂度为 O(n)\n",
    "print(seq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "seq.pop()\n",
    "print(seq) # 默认删除尾端元素，因而不需要移动元素，时间复杂度为O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "【2】remove 函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3]\n"
     ]
    }
   ],
   "source": [
    "seq.remove(2) # 首先需要扫描得到元素 “2”的下标，然后再删除，时间复杂度为 O(n)\n",
    "print(seq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 切片操作 O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3]\n",
      "[1, -1, -2, -3]\n"
     ]
    }
   ],
   "source": [
    "print(seq)\n",
    "seq[1:3] = [-1,-2,-3]\n",
    "print(seq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 拼接操作 O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, -1, -2, -3]\n",
      "[1, -1, -2, -3, 10, 20, 30]\n"
     ]
    }
   ],
   "source": [
    "print(seq)\n",
    "seq.extend([10,20,30]) # 将 [10,20,30] 与seq拼接\n",
    "print(seq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 排序操作 nlog(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, -1, -2, -3, 10, 20, 30]\n",
      "[-3, -2, -1, 1, 10, 20, 30]\n"
     ]
    }
   ],
   "source": [
    "print(seq)\n",
    "seq.sort()\n",
    "print(seq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 链接表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 定义： 将表中的元素存放在通过链接构造起来的一系列存储模块里，这样实现的表称为链接表，简称链表。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 单链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 单链表是由一些具体的结点组成，并且从头结点可以找到这个表里的任一个结点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 1> 结点\n",
    "\n",
    "<img src=\"image/chapter01/Node.jpg\" width=300>\n",
    "\n",
    "数据域存放元素，地址域存放下一元素的地址。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 定义一个 结点 类\n",
    "class LNode:\n",
    "    def __init__(self,elem,next_=None):\n",
    "        self.elem = elem\n",
    "        self.next = next_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 2> 单链表\n",
    "\n",
    "<img src=\"image/chapter01/danlianbiao.jpg\" width=600>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 要想掌握一个单链表，只需要用一个变量保存着该表的首结点的引用，我们把这样的变量称为头指针。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 优点：可以高效地通过删除结点来管理和释放内存，这是顺序表所不能比拟的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 缺点： 需要额外的容量存储地址，而且每一次删除和插入元素都要求找到被删除(插入）的前一结点。这是因为单链表只有一个方向的链接，对表中内容的一切检查都只能从表头开始。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 创建操作 O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a2'"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 初始化值\n",
    "def Linklist(*elem):  # elem 为需要存储的元素\n",
    "    p=L= LNode(None)\n",
    "    for e in elem:\n",
    "        L.next = LNode(e)\n",
    "        L = L.next\n",
    "    return p\n",
    "\n",
    "p = Linklist('a1','a2','a3') # p 就是单链表 p 的头指针\n",
    "p.next.next.elem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 插入操作 O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a3\n",
      "b1\n"
     ]
    }
   ],
   "source": [
    "# 在 a2 和 a3 之间插入 ‘b1’\n",
    "\n",
    "print(p.next.next.next.elem) \n",
    "a = p.next\n",
    "while a.elem != 'a2': # 需要先找到 'a2' 的位置\n",
    "    a = a.next\n",
    "\n",
    "b1 = LNode('b1')\n",
    "b1.next = a.next\n",
    "a.next = b1\n",
    "print(p.next.next.next.elem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 删除操作 O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b1\n",
      "a3\n"
     ]
    }
   ],
   "source": [
    "# 在 a2 和 a3 之间删除 ‘b1’\n",
    "\n",
    "print(p.next.next.next.elem) \n",
    "a = p.next\n",
    "while a.elem != 'a2': # 需要先找到 'a2' 的位置\n",
    "    a = a.next\n",
    "\n",
    "a.next = a.next.next\n",
    "print(p.next.next.next.elem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 遍历操作 O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a1\n",
      "a2\n",
      "a3\n"
     ]
    }
   ],
   "source": [
    "p = p.next\n",
    "while p is not None:\n",
    "    print(p.elem)\n",
    "    p = p.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 双链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 定义：在单链表的基础上，结点与结点之间不再是单向链接，而是双向链接，这样就得到了双链表。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 优点：从双链表中任一结点出发，就可以直接找到起前后相邻的结点，而对于单链表而已，它只能从表头开始逐一扫描得到。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 缺点：每个结点都需要增加一个链接域，增加的空间开销与结点数成正比，是O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 1> 结点\n",
    "\n",
    "<img src=\"image/chapter01/DNode.jpg\" width=500>\n",
    "\n",
    "数据域存放元素，前驱结点和后继结点分别存放上一和下一元素的地址。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DLNode(LNode):\n",
    "    def __init__(self,elem,prev=None,next_=None):\n",
    "        LNode.__init__(self,elem,next_)\n",
    "        self.prev = prev"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 2> 双链表\n",
    "\n",
    "<img src=\"image/chapter01/doublelianbiao.png\" width=600>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 创建操作 O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def DLinklist(*elem):\n",
    "    p = L = DLNode(None)\n",
    "    for e in elem:\n",
    "        L.next = DLNode(e)\n",
    "        L.next.prev = L\n",
    "        L = L.next\n",
    "    return p\n",
    "\n",
    "p = DLinklist('a0','a1','a2','a3')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 插入操作 O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a1\n",
      "b1\n"
     ]
    }
   ],
   "source": [
    "# 在 a0 和 a1 之间插入 'b1'\n",
    "print(p.next.next.elem)\n",
    "b1 = DLNode('b1')\n",
    "b1.next = p.next.next\n",
    "p.next.next.prev = b1\n",
    "p.next.next = b1\n",
    "b1.prev = p.next\n",
    "print(p.next.next.elem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 删除操作 O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b1\n",
      "a1\n"
     ]
    }
   ],
   "source": [
    "print(p.next.next.elem)\n",
    "p.next.next = p.next.next.next\n",
    "p.next.next.prev = p.next.next\n",
    "print(p.next.next.elem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 遍历操作 O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a0\n",
      "a1\n",
      "a2\n",
      "a3\n"
     ]
    }
   ],
   "source": [
    "p = p.next\n",
    "while p is not None:\n",
    "    print(p.elem)\n",
    "    p = p.next"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
